翻訳と辞書 Words near each other ・ Order-6 square tiling ・ Order-6 tetrahedral honeycomb ・ Order-6 triangular hosohedral honeycomb ・ Order-7 heptagonal tiling ・ Order-7 heptagrammic tiling ・ Order-7 hexagonal tiling honeycomb ・ Order-7 square tiling ・ Order-7 tetrahedral honeycomb ・ Order-7 triangular tiling ・ Order-8 hexagonal tiling ・ Order-8 octagonal tiling ・ Order-8 square tiling ・ Order-8 triangular tiling ・ Order-embedding ・ Order-independent transparency ・ Order-maintenance problem ・ OrderAhead ・ Ordered Bell number ・ Ordered dithering ・ Ordered exponential ・ Ordered field ・ Ordered from the Catalogue ・ Ordered geometry ・ Ordered graph ・ Ordered list ・ Ordered logit ・ Ordered pair ・ Ordered probit ・ Ordered ring ・ Ordered semigroup Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Order-maintenance problem ： ウィキペディア英語版 Order-maintenance problem In Computer Science the Order-Maintenance Problem involves maintaining a totally ordered set supporting the following operations: * insert(X, Y), which inserts X immediately after Y in the total order; * order(X, Y), which determines if X precedes Y in the total order; and * delete(X), which removes X from the set. The first data structure for order-maintenance was given by Dietz in 1982.〔.〕 This data structure supports insert(X, Y) in $O(\backslash log\; n)$ amortized time and order(X, Y) in constant time but does not support deletion. Tsakalidis published a data structure in 1984 based on BB() trees with the same performance bounds that supports deletion in $O(\backslash log\; n)$ and showed how indirection can be used to improve insertion and deletion performance to $O(1)$ amortized time.〔.〕 In 1987 Dietz and Sleator published the first data structure supporting all operations in worst-case constant time.〔name="DietzSleator">. Full version, (Tech. Rep. CMU-CS-88-113 ), Carnegie Mellon University, 1988.〕 Efficient data structures for order-maintenance have applications in many areas, including data structure persistence,〔name="Driscoll">.〕 graph algorithms〔name="Eppstein">.〕〔.〕 and fault-tolerant data structures.〔name="Aumann">.〕 ==List-labeling== A problem related to the order-maintenance problem is the ''list-labeling problem'' in which instead of the order(X, Y) operation the solution must maintain an assignment of labels from a universe of integers $\backslash$ to the elements of the set such that X precedes Y in the total order if and only if X is assigned a lesser label than Y. It must also support an operation label(X) returning the label of any node X. Note that order(X, Y) can be implemented simply by comparing label(X) and label(Y) so that any solution to the list-labeling problem immediately gives one to the order-maintenance problem. In fact, most solutions to the order-maintenance problem are solutions to the list-labeling problem augmented with a level of data structure indirection to improve performance. We will see an example of this below. For efficiency, it is desirable for the size $u$ of the universe be bounded in the number of elements $n$ stored in the data structure. In the case where $u$ is required to be linear in $n$ the problem is known as the ''packed-array maintenance'' or ''dense sequential file maintenance'' problem. Consider the elements as entries in a file and the labels as giving the addresses where each element is stored. Then an efficient solution to the packed-array maintenance problem would allow efficient insertions and deletions of entries into the middle of a file with no asymptotic space overhead.〔.〕〔.〕〔name="WillardGood">.〕〔.〕〔name="WillardMaint">.〕 This usage has recent applications in cache-oblivious data structures〔.〕 and optimal worst-case in-place sorting.〔name="Franceschini">.〕 However, under some restrictions, $\backslash Omega(\backslash log^2\; n)$ lower bounds have been found on the performance of insertion in solutions of the list-labeling problem with linear universes〔name="DietzZhang">.〕 whereas we will see below that a solution with a polynomial universe can perform insertions in $O(\backslash log\; n)$ time. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Order-maintenance problem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.